package com.zhou.xin.test.algorithm;

import java.util.Scanner;

/**
 * @author ZhouXin
 * @ClassName SearchAlgorithm
 * @description: 查找算法
 * @date 2023年12月12日
 * @version: 1.0
 */
public class SearchAlgorithm {

    /**
     * @description 线性查找
     * @param num 查找的数字
     * @param arr 查找的数组
     * @return java.lang.String
     * @date 2023/12/12 17:01
     **/
    public static String linearSearch(int num, int[] arr) {
        if (arr == null || arr.length == 0){
            return "数组为空";
        }
        for (int n : arr) {
            if (num == n) {
                return "数字在数组里面";
            }
        }
        return "数字不在数组里面！";
    }

    /**
     * @description 二分查找
     * @param num 查找的数字
     * @param arr 查找的数组
     * @return java.lang.String
     * @date 2023/12/12 17:19
     **/
    public static String binarySearch(int num, int[] arr) {
        if (arr == null || arr.length == 0) {
            return "数组为空";
        }
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == num) {
                return "数字在数组里面";
            } else if (arr[mid] < num) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return "数字不在数组里面";
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("请输入一个数字(按Enter继续)：");
        int[] arr = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024};
        String tips = binarySearch(input.nextInt(), arr);
        System.out.println(tips);
    }
}
